package com.zxy.leetcode._00000_00099._00080_00089;

import com.zxy.leetcode.common.ListNode;
import com.zxy.leetcode.common.ListNodeHelper;

/**
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
 *
 * 删除排序链表中的重复元素 II
 *
 * 给定一个排序链表，删除所有含有重复数字的节点，
 * 只保留原始链表中 没有重复出现 的数字。
 *
 * 例子
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 */
public class Test00082 {

    public static void main(String[] args) {
        Test00082 test = new Test00082();
        int[] nums = {1, 2, 3, 3, 4, 4, 5};
        ListNode head = ListNodeHelper.build(nums);
        test.deleteDuplicates(head);
        ListNodeHelper.print(head);
    }

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 可能开头就有相同元素了，在head前面加一个节点，统一处理
        ListNode beforeHeadNode = new ListNode(0, head);

        ListNode pre = beforeHeadNode;
        ListNode p = head.next;
        int val = head.val;
        boolean flag = true;

        while (p != null) {
            if (val == p.val) {
                // 相同就删除
                pre.next = p.next;
                flag = false;
            }else {
                /*
                 针对 1 2 2 3 3 4，这种数据进行处理，
                 删除了2，pre还不能next，因为3还需要被删除
                 pre需要保持在1这里，后续的循环才能让1的next为4
                  */
                if (flag) {
                    pre = pre.next;
                }
                flag = true;
                val = p.val;
            }
            p = p.next;
        }

        return beforeHeadNode.next;
    }
}
